package org.example.graph_theory;

import java.util.Arrays;

public class The_number_of_enclaves {
    public static void main(String[] args) {
        //飞地的数量

        //给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
        //一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
        //返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
//        int[][] grid = {{0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0}};
//        int[][] grid = {{0},{1},{1},{0},{0}};
        int[][] grid = {
                {0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1},
                {1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0},
                {1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1},
                {1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1},
                {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1},
                {0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0},
                {0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0},
                {1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
                {1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0}
        };
        int[][] te = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1},
                {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0},
                {0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        };
        int i = numEnclaves(grid);
        System.out.println(i);
    }

    public static int numEnclaves(int[][] grid) {
        int num = 0;
        if (grid.length >= 3 && grid[0].length >= 3) {
            for (int i = 0; i < grid[0].length; i++) {
                if (grid[0][i] == 1) {
                    dfs(grid, 0, i);
                }
            }
            for (int i = 0; i < grid[grid.length - 1].length; i++) {
                if (grid[grid.length - 1][i] == 1) {
                    dfs(grid, grid.length - 1, i);
                }
            }
            for (int i = 0; i < grid.length; i++) {
                if (grid[i][0] == 1) {
                    dfs(grid, i, 0);
                }
            }
            for (int i = 0; i < grid.length; i++) {
                if (grid[i][grid[0].length - 1] == 1) {
                    dfs(grid, i, grid[0].length - 1);
                }
            }

            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == 1) {
                        num++;
                    }
                }
            }
        }
        System.out.println(Arrays.deepToString(grid));
        return num;
    }

    public static void dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == 0) return;
        grid[i][j] = 0;
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}
